/*  两个队列实现一个栈
 *  主要的思想：
 *    入栈：队列1INSERT
 *    出栈：队列1为空，若队列2为空，则underflow；
 *                  队列2不为空，队列2前n-1个元素DELETE，同时队列1INSERT，最后队列2中第n个元素即为出栈元素
 *         队列1不为空，将队列1前n-1中元素DELETE，同时队列2INSERT
 *         最后队列1中第n个元素即为出栈元素
 * */

#include <iostream>
#include <queue>

template <typename T> class CStack{
public:
    CStack(void);
    ~CStack(void);

    void push(const T& node);
    T pop();

private:
    std::queue<T> queue1;
    std::queue<T> queue2;
};

template <typename T>
CStack<T>::CStack() {
    std::cout << "create a stack" << std::endl;
}

template <typename T>
CStack<T>::~CStack() {
    std::cout << "destroy a stack" << std::endl;
}

template <typename T>
void CStack<T>::push(const T& node){
    if(queue1.empty() && queue2.empty()){
        queue1.push(node);
    }else if(queue1.empty()){
        queue2.push(node);
    }else if(queue2.empty()){
        queue1.push(node);
    }
}

template <typename T>
T CStack<T>::pop() {
    if(queue1.empty() && queue2.empty()){
        throw "underflow";
    }else if(queue1.empty()){
        int length = queue2.size() - 1;
        for(int i=0; i<length; i++){
            T t = queue2.front();
            queue1.push(t);
            queue2.pop();
        }
        T rt = queue2.front();
        queue2.pop();
        return rt;
    }else if(queue2.empty()){
        int length = queue1.size() - 1;
        for(int i=0; i<length; i++){ //队列的长度注意 queue.size()动态变化
            T t = queue1.front();
            queue2.push(t); //队列2的INSERT必须在队列1的DELETE之前，不然t就变为了队列1DELETE之后的队首元素 strange
            queue1.pop();
        }
        T rt = queue1.front();
        queue1.pop();
        return rt;
    }
}

int main() {
    CStack<int> ex;
    try {
        ex.push(1);
        ex.push(2);
        std::cout << ex.pop() << std::endl;
        std::cout << ex.pop() << std::endl;
//        std::cout << ex.pop() << std::endl;
        ex.push(5);
        ex.push(8);
        ex.push(9);
        std::cout << ex.pop() << std::endl;
        std::cout << ex.pop() << std::endl;
        std::cout << ex.pop() << std::endl;
    }catch(const char* msg){
        std::cout << msg << std::endl;
    }
    return 0;
}